// UVa12661 - Funny Car Racing
// 刘汝佳
#include <bits/stdc++.h>
using namespace std;
const int VV = 304, INF = 1e9;
typedef pair<int, int> IPair;  // D[u]: D

struct Edge {
  int from, to, open, close, w;
};

vector<Edge> G[VV];
int N, M, S, T, D[VV];
int arrive(int t, const Edge& e) {  //从到达道路e起点的时间t到达道路e终点时间
  int k = t % (e.open + e.close);         // e.w <= open
  if (k + e.w <= e.open) return t + e.w;  // x--t+e.w--x+a-----x+b
  return t + e.open + e.close - k + e.w;  // x--x+a--t+e.w--x+b
}

void Dijkstra() {
  priority_queue<IPair, vector<IPair>, greater<IPair>> Q;
  fill(D, D + VV, INF), D[S] = 0, Q.push(make_pair(0, S));
  while (!Q.empty()) {
    IPair p = Q.top();
    Q.pop();
    int u = p.second, d = p.first;
    if (D[u] != d) continue;  // d的最短路已经算出来了
    for (size_t i = 0; i < G[u].size(); i++) {
      const Edge& e = G[u][i];
      int v = e.to, &dv = D[e.to], nd = arrive(D[u], e);  //到达e.to的时间
      if (dv > nd) dv = nd, Q.push({dv, v});
    }
  }
}

int main() {
  for (int kase = 1; scanf("%d%d%d%d", &N, &M, &S, &T) == 4; ++kase) {
    for (int i = 0; i <= N; i++) G[i].clear();
    for (int i = 0, u, v, a, b, t; i < M; i++) {
      scanf("%d%d%d%d%d", &u, &v, &a, &b, &t);
      if (t > a) continue;  // 通过用时比开放时间长
      G[u].push_back({u, v, a, b, t});
    }
    Dijkstra();
    printf("Case %d: %d\n", kase, D[T]);
  }
  return 0;
}
/*
算法分析请参考: 《入门经典-第2版》例题11-11
注意本题在Dijkstra算法中边的存在性与当前的d值有关
*/
// Accepted 40ms 1466 C++5.3.0 2020-12-14 17:52:16 25846643